#include <iostream>
#include <vector>
using namespace std;

int max_value_recur(vector<int> &c, vector<int> &w, int n, int m)
{
        if(n == 0){
                return 0;
        }

        int max_value = max_value_recur(c, w, n - 1, m);
        if(m >= w[n]){
                max_value = max(max_value, max_value_recur(c, w, n - 1, m - w[n]) + c[n]);
        }

        return max_value;
}

int max_value_dp(vector<int> &c, vector<int> &w, int n, int m)
{
        vector<int> dp(m + 1, 0);
        for(int i = 1; i <= n; i++){
                for(int j = m; j >= w[i]; j--){
                        dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
                }
        }

        return dp.back();
}

int main()
{
        int n, m;
        cin>>n>>m;
        vector<int> c(n + 1, 0), w(c);
        for(int i = 1; i <= n; i++){
                cin>>w[i]>>c[i];
        }
        cout<<max_value_dp(c, w, n, m)<<endl;
        return 0;
}